import java.util.Arrays;

public class Test {
    public static void main(String[] args) {
        int[] arr = {1,2,34,3,4,5,7,23,12};
        int[] arr1 = {2,6,4,1};
        System.out.println(threeConsecutiveOdds(arr));
        System.out.println(threeConsecutiveOdds(arr1));
    }

    //给你一个整数数组 arr，请你判断数组中是否存在连续三个元素都是奇数的情况
    //如果存在，请返回 true ；否则，返回 false
    public static boolean threeConsecutiveOdds(int[] arr){
        int count = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] % 2 != 0){
                count ++;
                if (count == 3){
                    return true;
                }
            }else {
                count = 0;
            }
        }
        return false;
    }

    public static void main7(String[] args) {
        int[] nums = {3,2,3};
        System.out.println(majorityElement(nums));
    }

    //给定一个大小为 n 的数组，找到其中的多数元素
    //排序法,将数组排序后，数组 n/2 的元素一定是众数
    public static int majorityElement(int[] nums){
        Arrays.sort(nums);
        return nums[nums.length/2];
    }

    public static void main6(String[] args) {
        int[] nums = {0,1,2,1,2};
        System.out.println(singleNumber(nums));
    }

    //给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素
    //异或的特点是：
    //1、n ^ n = 0；即两个相同的数字异或是0
    //2、0 ^ n = n；即0和任何数字进行异或，结果就是那个任何数字
    public static int singleNumber(int[] nums){
        int ret = 0;
        for (int i : nums){
            ret ^= i;
        }
        return ret;
    }

    public static void main5(String[] args) {
        int[] nums = {2, 7, 11, 15};
        System.out.println(Arrays.toString(twoSum(nums,9)));
    }

    //给定一个整数数组 nums 和一个整数目标值 target
    //在数组中找出和为目标值的两个整数,并返回它们的数组下标
    public static int[] twoSum(int[] nums,int target){
        int[] result = new int[2];
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = nums.length-1; j > i ; j--) {
                if (nums[i] + nums[j] == target){
                    result[0] = i;
                    result[1] = j;
                }
            }
        }
        return result;
    }

    public static void main4(String[] args) {
        int[] arrays = {1,2,3,4,5,6};
        System.out.println(binarySearch(arrays, 6));
    }

    //给定一个有序整型数组, 实现二分查找
    public static int binarySearch(int[] arrays,int key){
        int left = 0;
        int right = arrays.length-1;
        while (left <= right){
            int mid = (left + right) / 2;
            if (arrays[mid] == key){
                return mid;
            } else if (arrays[mid] < key) {
                left = mid + 1;
            }else {
                right = mid - 1;
            }
        }
        return -1;
    }

    public static void main3(String[] args) {
        int[] arrays = {1,2,3,4,5,6};
        func3(arrays);
        System.out.println(Arrays.toString(arrays));
    }

    //奇数位于偶数之前调整数组顺序使得奇数位于偶数之前。调整之后，不关心大小顺序。
    //如数组：[1,2,3,4,5,6] 调整后可能是：[1, 5, 3, 4, 2, 6]
    public static void func3(int[] arrays){
       int i = 0;
       int j = arrays.length-1;
       while (i < j){
           //如果数组都是奇数，i要走到和j相遇，因此是i本身应该是一个单独的循环
           while (i < j && arrays[i] % 2 != 0){
               i++;
           }
           while (i < j && arrays[j] % 2 == 0){
               j--;
           }
           int tmp = arrays[i];
           arrays[i] = arrays[j];
           arrays[j] = tmp;
       }
    }

    //改变原有数组元素的值
    //实现一个方法 transform, 以数组为参数, 循环将数组中的每个元素乘以 2 ,
    //并设置到对应的数组元素上. 例如 原数组为 {1, 2, 3}, 修改之后为 {2, 4, 6}

    //方式一：扩大的还是原来的数组，这样做的不好的地方是，改变了原来数组的值
    public static void func1(int[] arrays){
        for (int i = 0; i < arrays.length; i++) {
            arrays[i] = 2*arrays[i];
        }
    }

    //扩大的新的数组，没有修改原来的值
    public static void func2(int[] arrays){
        int[] tmp = new int[arrays.length];
        for (int i = 0; i < arrays.length; i++) {
            tmp[i] = arrays[i] * 2;
        }
    }

    public static void main2(String[] args) {
        hanoi(3,'A','B','C');
    }

    //递归求解汉诺塔问题
    public static void move(char pos1,char pos2){
        //表示一个盘子从一个位置移动到另一个位置
        System.out.print(pos1 + "->" + pos2 + " ");
    }

    //n是盘子数，第一个盘子pos1是起始地，第二个盘子pos2是中转地，第三个盘子pos3是目的地
    public static void hanoi(int n,char pos1,char pos2,char pos3){
        if (n == 1){
            //只有一个盘子直接放入目的地
            move(pos1,pos3);
        }else {
            //把起始地pos1上面n-1个盘子通过pos3中转放到pos2
            hanoi(n-1,pos1,pos3,pos2);
            //把起始地最后一个盘子放入目的地
            move(pos1,pos3);
            //此时将pos2上面一共有n-1个盘子通过pos1中转放到pos3完成任务
            hanoi(n-1,pos2,pos1,pos3);
        }
    }

    public static void main1(String[] args) {
        int[] arrays = {1,2,3,4,556,6};
        bubbleSort(arrays);
        System.out.println(Arrays.toString(arrays));
        reverse(arrays);
        System.out.println(Arrays.toString(arrays));
        avg(arrays);
        System.out.println(avg(arrays));
    }

    //求数组平均值
    public static double avg(int[] arrays){
        int sum = 0;
        for (int x:arrays){
            sum += x;
        }
        return (double) sum / (double) arrays.length;
    }

    //数组逆序
    public static void reverse(int[] arrays){
        if (arrays == null){
            return;
        }
        int i = 0;
        int j = arrays.length-1;
        while (i < j){
            int tmp = arrays[i];
            arrays[i] = arrays[j];
            arrays[j] = tmp;
            i++;
            j--;
        }
    }

    //冒泡排序
    public static void bubbleSort(int[] arrays){
        if (arrays == null){
            return;
        }
        //i 代表趟数
        for (int i = 0; i < arrays.length - 1; i++) {
            boolean flg = false;
            //进行交换
            for (int j = 0; j < arrays.length - 1 - i; j++) {
                if (arrays[j] > arrays[j+1]){
                    int tmp = arrays[j];
                    arrays[j] = arrays[j+1];
                    arrays[j+1] = tmp;
                    flg = true;
                }
            }
            //！为非，结果为 boolean 类型，非假即为真，执行语句
            if (!flg){
                //flg = false ，没有进行交换
                return;
            }
        }
    }
}
